/* -*- mode: C -*-  */
/* 
   IGraph library.
   Copyright (C) 2003-2012  Gabor Csardi <csardi.gabor@gmail.com>
   334 Harvard street, Cambridge, MA 02139 USA
   
   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2 of the License, or
   (at your option) any later version.
   
   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.
   
   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 
   02110-1301 USA

*/

#include "igraph_memory.h"
#include "igraph_random.h"
#include "igraph_error.h"
#include "config.h"

#include <assert.h>
#include <string.h> 		/* memcpy & co. */
#include <stdlib.h>

/** 
 * \section igraph_dqueue
 * <para>
 * This is the classic data type of the double ended queue. Most of
 * the time it is used if a First-In-First-Out (FIFO) behavior is
 * needed. See the operations below.
 * </para>
 * 
 * <para>
 * \example examples/simple/dqueue.c
 * </para>
 */

/**
 * \ingroup dqueue
 * \function igraph_dqueue_init
 * \brief Initialize a double ended queue (deque).
 * 
 * The queue will be always empty.
 * \param q Pointer to an uninitialized deque.
 * \param size How many elements to allocate memory for. 
 * \return Error code.
 * 
 * Time complexity: O(\p size).
 */

int FUNCTION(igraph_dqueue,init) (TYPE(igraph_dqueue)* q, long int size) {
        assert(q != 0);
	if (size <= 0 ) { size=1; }
	q->stor_begin=igraph_Calloc(size, BASE);
	if (q->stor_begin==0) {
	  IGRAPH_ERROR("dqueue init failed", IGRAPH_ENOMEM);
	}
	q->stor_end=q->stor_begin + size;
	q->begin=q->stor_begin;
	q->end=NULL;
	
	return 0;
}

/**
 * \ingroup dqueue
 * \function igraph_dqueue_destroy
 * \brief Destroy a double ended queue.
 * 
 * \param q The queue to destroy
 * 
 * Time complexity: O(1).
 */

void FUNCTION(igraph_dqueue,destroy) (TYPE(igraph_dqueue)* q) {
  assert(q != 0);
  if (q->stor_begin != 0) {
    igraph_Free(q->stor_begin);
    q->stor_begin=0;
  }
}

/**
 * \ingroup dqueue
 * \function igraph_dqueue_empty
 * \brief Decide whether the queue is empty.
 * 
 * \param q The queue.
 * \return Boolean, \c TRUE if \p q contains at least one element, \c
 * FALSE otherwise.
 * 
 * Time complexity: O(1).
 */

igraph_bool_t FUNCTION(igraph_dqueue,empty) (const TYPE(igraph_dqueue)* q) {
  assert(q != 0);
  assert(q->stor_begin != 0);
  return q->end == NULL;
}

/**
 * \ingroup dqueue
 * \function igraph_dqueue_clear
 * \brief Remove all elements from the queue.
 * 
 * \param q The queue
 * 
 * Time complexity: O(1).
 */

void FUNCTION(igraph_dqueue,clear)   (TYPE(igraph_dqueue)* q) {
  assert(q != 0);
  assert(q->stor_begin != 0);
  q->begin=q->stor_begin;
  q->end=NULL;
}

/**
 * \ingroup dqueue
 * \function igraph_dqueue_full
 * \brief Check whether the queue is full.
 *
 * If a queue is full the next igraph_dqueue_push() operation will allocate
 * more memory.
 * \param q The queue.
 * \return \c TRUE if \p q is full, \c FALSE otherwise.
 * 
 * Time complecity: O(1).
 */

igraph_bool_t FUNCTION(igraph_dqueue,full) (TYPE(igraph_dqueue)* q) {
  assert(q != 0);
  assert(q->stor_begin != 0);
  return q->begin == q->end;
}

/**
 * \ingroup dqueue
 * \function igraph_dqueue_size
 * \brief Number of elements in the queue.
 * 
 * \param q The queue.
 * \return Integer, the number of elements currently in the queue.
 * 
 * Time complexity: O(1).
 */

long int FUNCTION(igraph_dqueue,size) (const TYPE(igraph_dqueue)* q) {
        assert(q != 0);
        assert(q->stor_begin != 0);
	if (q->end==NULL) {
		return 0;
	} else if (q->begin < q->end) {
		return q->end - q->begin;
	} else {
		return q->stor_end - q->begin + q->end - q->stor_begin;
	}
}

/**
 * \ingroup dqueue
 * \function igraph_dqueue_head
 * \brief Head of the queue.
 * 
 * The queue must contain at least one element.
 * \param q The queue.
 * \return The first element in the queue.
 * 
 * Time complexity: O(1).
 */

BASE FUNCTION(igraph_dqueue,head) (const TYPE(igraph_dqueue)* q) {
        assert(q != 0);
	assert(q->stor_begin != 0);
	return *(q->begin);
}

/**
 * \ingroup dqueue
 * \function igraph_dqueue_back
 * \brief Tail of the queue.
 * 
 * The queue must contain at least one element.
 * \param q The queue.
 * \return The last element in the queue.
 * 
 * Time complexity: O(1).
 */

BASE FUNCTION(igraph_dqueue,back) (const TYPE(igraph_dqueue)* q) {
        assert(q != 0);
	assert(q->stor_begin != 0);
	if (q->end == q->stor_begin)
		return *(q->stor_end-1);
	return *(q->end-1);
}

/**
 * \ingroup dqueue
 * \function igraph_dqueue_pop
 * \brief Remove the head.
 * 
 * Removes and returns the first element in the queue. The queue must
 * be non-empty.
 * \param q The input queue.
 * \return The first element in the queue.
 * 
 * Time complexity: O(1).
 */

BASE FUNCTION(igraph_dqueue,pop) (TYPE(igraph_dqueue)* q) {
	BASE tmp=*(q->begin);
        assert(q != 0);
	assert(q->stor_begin != 0);
	(q->begin)++;
	if (q->begin==q->stor_end) {
		q->begin=q->stor_begin;
	}
	if (q->begin==q->end) {
		q->end=NULL;
	}

	return tmp;
}

/**
 * \ingroup dqueue
 * \function igraph_dqueue_pop_back
 * \brief Remove the tail
 *
 * Removes and returns the last element in the queue. The queue must
 * be non-empty.
 * \param q The queue.
 * \return The last element in the queue.
 * 
 * Time complexity: O(1).
 */

BASE FUNCTION(igraph_dqueue,pop_back) (TYPE(igraph_dqueue)* q) {
	BASE tmp;
        assert(q != 0);
	assert(q->stor_begin != 0);
	if (q->end != q->stor_begin) {
		tmp=*((q->end)-1);
		q->end = (q->end)-1;
	} else {
		tmp=*((q->stor_end)-1);
		q->end = (q->stor_end)-1;
	}
	if (q->begin==q->end) {
		q->end=NULL;
	}
	
	return tmp;
}

/**
 * \ingroup dqueue
 * \function igraph_dqueue_push
 * \brief Appends an element.
 *
 * Append an element to the end of the queue.
 * \param q The queue.
 * \param elem The element to append.
 * \return Error code.
 *
 * Time complexity: O(1) if no memory allocation is needed, O(n), the
 * number of elements in the queue otherwise. But not that by
 * allocating always twice as much memory as the current size of the
 * queue we ensure that n push operations can always be done in at
 * most O(n) time. (Assuming memory allocation is at most linear.)
 */

int FUNCTION(igraph_dqueue,push) (TYPE(igraph_dqueue)* q, BASE elem) {
        assert(q != 0);
	assert(q->stor_begin != 0);
	if (q->begin != q->end) {
		/* not full */
		if (q->end==NULL) {
			q->end=q->begin;
		}			
		*(q->end) = elem;
		(q->end)++;
		if (q->end==q->stor_end) {
			q->end=q->stor_begin;
		}
	} else {
		/* full, allocate more storage */
		
		BASE *bigger=NULL, *old=q->stor_begin;

		bigger=igraph_Calloc( 2*(q->stor_end - q->stor_begin)+1, BASE );
		if (bigger==0) {
		  IGRAPH_ERROR("dqueue push failed", IGRAPH_ENOMEM);
		}

		if (q->stor_end - q->begin) {
			memcpy(bigger, q->begin, 
			       (size_t)(q->stor_end - q->begin) * sizeof(BASE));
		}
		if (q->end - q->stor_begin > 0) {
			memcpy(bigger + (q->stor_end - q->begin), q->stor_begin,
			       (size_t)(q->end - q->stor_begin) * sizeof(BASE));
		}
		
		q->end       =bigger + (q->stor_end - q->stor_begin);
		q->stor_end  =bigger + 2*(q->stor_end - q->stor_begin) + 1;
		q->stor_begin=bigger;
		q->begin     =bigger;
				
		*(q->end) = elem;
		(q->end)++;
		if (q->end==q->stor_end) {
			q->end=q->stor_begin;
		}

		igraph_Free(old);
	}
	
	return 0;
}

#if defined (OUT_FORMAT)

#ifndef USING_R
int FUNCTION(igraph_dqueue,print)(const TYPE(igraph_dqueue)* q) {
  return FUNCTION(igraph_dqueue,fprint)(q, stdout);
}
#endif

int FUNCTION(igraph_dqueue,fprint)(const TYPE(igraph_dqueue)* q, FILE *file) {
  if (q->end != NULL) {
    /* There is one element at least */
    BASE *p=q->begin;
    fprintf(file, OUT_FORMAT, *p);
    p++;
    if (q->end > q->begin) {
      /* Q is in one piece */
      while (p != q->end) {
	fprintf(file, " " OUT_FORMAT, *p);
	p++;
      }
    } else {
      /* Q is in two pieces */
      while (p != q->stor_end) {
	fprintf(file, " " OUT_FORMAT, *p);
	p++;
      }
      p=q->stor_begin;
      while (p != q->end) {
	fprintf(file, " " OUT_FORMAT, *p);
	p++;
      }
    }
  }

  fprintf(file, "\n");

  return 0;
}

#endif

BASE FUNCTION(igraph_dqueue,e)(const TYPE(igraph_dqueue) *q, long int idx) {
  if ((q->begin + idx < q->end) ||
      (q->begin >= q->end && q->begin+idx < q->stor_end)) {
    return q->begin[idx];
  } else if (q->begin >= q->end && q->stor_begin+idx < q->end) {
    idx = idx-(q->stor_end - q->begin);
    return q->stor_begin[idx];
  } else {
    return 0;			/* Error */
  }
}
